
Namespace std

    'just confirm keyType is comparable to itself
    Public MustInherit Class xtree(Of keyType As IComparable(Of keyType))
        Implements ICloneable

        Public Class iterator
            Inherits randomAccessIterator(Of node)

            'help to do traversal with a prev boolean value
            Private Shared Sub jmpNode(ByRef iterator As node, ByVal left As Boolean)
                iterator = findNode(iterator, left)
            End Sub

            Private Shared Function findNode(ByRef iterator As node, ByVal left As Boolean) As node
                If left Then
                    Return iterator.lchild
                Else
                    Return iterator.rchild
                End If
            End Function

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If p Is Nothing Then
                    Return False
                End If

                If Not findNode(p, prev) Is Nothing Then
                    jmpNode(p, prev)
                    If prev Then
                        max(p)
                    Else
                        min(p)
                    End If
                ElseIf Not p.father Is Nothing Then
                    If p Is findNode(p.father, Not prev) Then
                        p = p.father
                    Else
                        While p Is findNode(p.father, prev)
                            p = p.father
                            If p.father Is Nothing Then
                                Exit While
                            End If
                        End While
                        p = p.father
                    End If
                Else
                    p = _end.p
                End If

                Return p <> _end
            End Function

            Public Sub New()
                MyBase.New()
            End Sub

            Public Sub New(ByVal that As pointer(Of node))
                MyBase.New(that)
            End Sub

            Public Sub New(ByVal that As iterator)
                MyBase.New(that.p)
            End Sub

            Public Sub New(ByVal that As node)
                MyBase.New(that)
            End Sub

            Public Overloads Shared Operator +(ByVal this As iterator) As keyType
                If this Is Nothing Then
                    Return Nothing
                Else
                    Return +(this.instance())
                End If
            End Operator
        End Class

        Public Class node
            Inherits pointernode(Of keyType)
            Implements IComparable(Of node)

            Public Const _pointerCount As Int64 = 3

            Private Class pointerIndex
                Public Const father As Int64 = 0
                Public Const lchild As Int64 = 1
                Public Const rchild As Int64 = 2
            End Class

            Public Sub clearfather()
                appendfather(Nothing)
            End Sub

            Public Function father() As node
                Return pointer(pointerIndex.father)
            End Function

            Public Function lchild() As node
                Return pointer(pointerIndex.lchild)
            End Function

            Public Function rchild() As node
                Return pointer(pointerIndex.rchild)
            End Function

            Private Sub appendfather(ByVal value As node)
                debugassert(Not Object.ReferenceEquals(value, Me), "should not append father to a node itself.")
                pointer(pointerIndex.father) = value
            End Sub

            Public Sub appendleft(ByVal value As node)
                debugassert(Not Object.ReferenceEquals(value, Me), "should not append left to a node itself.")
                pointer(pointerIndex.lchild) = value
                If Not value Is Nothing Then
                    value.appendfather(Me)
                End If
            End Sub

            Public Sub appendright(ByVal value As node)
                debugassert(Not Object.ReferenceEquals(value, Me), "should not append left to a node itself.")
                pointer(pointerIndex.rchild) = value
                If Not value Is Nothing Then
                    value.appendfather(Me)
                End If
            End Sub

            Public Sub New(ByVal that As keyType)
                MyBase.New(_pointerCount, that)
            End Sub

            Public Sub New()
                MyBase.New(_pointerCount)
            End Sub

            Public Overloads Function CompareTo(ByVal other As node) As Int32 Implements IComparable(Of node).CompareTo
                Return MyBase.CompareTo(other)
            End Function
        End Class

        Private _root As node
        Private nodeCount As Int64
        Private Shared _end As iterator

        Protected Property root() As node
            Get
                Return _root
            End Get
            Set(ByVal value As node)
                _root = value
                If Not _root Is Nothing Then
                    _root.clearfather()
                End If
            End Set
        End Property

#If RETIRED Then
        Private Shared Sub deleteTree(ByRef root As node)
            If Not root Is Nothing Then
                deleteTree(root.lchild())
                root.appendleft(Nothing)
                deleteTree(root.rchild())
                root.appendright(Nothing)
                root = Nothing
            End If
        End Sub
#End If

        Private Shared Function min(ByRef iterator As node) As Boolean
            If iterator Is Nothing Then
                Return False
            Else
                While Not iterator.lchild Is Nothing
                    iterator = iterator.lchild
                End While
                Return True
            End If
        End Function

        Private Shared Function max(ByRef iterator As node) As Boolean
            If iterator Is Nothing Then
                Return False
            Else
                While Not iterator.rchild Is Nothing
                    iterator = iterator.rchild
                End While
                Return True
            End If
        End Function

        Private Function [erase](ByVal iterator As node) As Boolean
            If iterator Is Nothing Then
                Return False
            Else
                Dim isLeftChild As Boolean = False
                Dim isRightChild As Boolean = False
                Dim newSubTree As node = Nothing
                If Not (iterator.father Is Nothing) Then
                    If Object.ReferenceEquals(iterator.father.lchild, iterator) Then
                        isLeftChild = True
                    Else
                        assert(Object.ReferenceEquals(iterator.father.rchild, iterator) _
                                    , "iterator.father.right is not iterator.")
                        isRightChild = True
                    End If
                Else
                    debugassert(Object.ReferenceEquals(iterator, root) _
                                , "iterator is not root, but does not have father node.")
                End If

                If (iterator.lchild Is Nothing) AndAlso (iterator.rchild Is Nothing) Then
                    newSubTree = Nothing
                ElseIf iterator.lchild Is Nothing Then
                    newSubTree = iterator.rchild
                ElseIf iterator.rchild Is Nothing Then
                    newSubTree = iterator.lchild
                Else
                    If rnd(0, 2, True) = 0 Then
                        newSubTree = iterator.lchild
                        debugassert(max(newSubTree), "cannot get max right sub tree.")
                        newSubTree.appendright(iterator.rchild)
                        newSubTree = iterator.lchild
                    Else
                        newSubTree = iterator.rchild
                        debugassert(min(newSubTree), "cannot get min left sub tree.")
                        newSubTree.appendleft(iterator.lchild)
                        newSubTree = iterator.rchild
                    End If
                End If

                If isLeftChild Then
                    iterator.father.appendleft(newSubTree)
                ElseIf isRightChild Then
                    iterator.father.appendright(newSubTree)
                Else
                    root = newSubTree
                End If
                nodeCount -= 1

                iterator.clear()
                iterator = Nothing
                Return True
            End If
        End Function

        Public Function [erase](ByVal it As iterator) As Boolean
            Return [erase](it.instance())
        End Function

        Public Function [erase](ByVal key As keyType) As Boolean
            Return [erase](find(key))
        End Function

        Public Function find(ByVal key As keyType) As iterator
            Dim work As node = root
            Dim cmp As Int32
            While Not (work Is Nothing)
                cmp = compare(+work, key)
                If cmp < 0 Then
                    work = work.rchild
                ElseIf cmp > 0 Then
                    work = work.lchild
                Else
                    Exit While
                End If
            End While

            Return New iterator(work)
        End Function

        Public Sub clear()
            'mark, i do not need to delete all elements in fact.
            'deleteTree(root)
            root = Nothing
            nodeCount = 0
        End Sub

        Public Function empty() As Boolean
            debugassert((root Is Nothing) = (size() = 0), "(root Is Nothing) <> (size() = 0)")
            Return root Is Nothing
        End Function

        Public Function begin() As iterator
            Dim work As node = root
            min(work)

            Return New iterator(work)
        End Function

        Public Function rbegin() As iterator
            Dim work As node = root
            max(work)

            Return New iterator(work)
        End Function

        Public Shared Function shared_end() As iterator
            Return _end
        End Function

        Public Shared Function shared_rend() As iterator
            Return _end
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function rend() As iterator
            Return _end
        End Function

        Public Function size() As Int64
            Return nodeCount
        End Function

        Public Function insert(ByVal k As keyType) As iterator
            Return insert(New node(k))
        End Function

        Public Function insert(ByVal that As xtree(Of keyType)) As Boolean
            If that Is Nothing Then
                Return False
            Else
                Dim i As xtree(Of keyType).iterator = Nothing
                i = that.begin()
                While i <> that.end()
                    debugassert(insert(i) <> [end](), "insert(i) returns false.")
                    i += 1
                End While

                Return True
            End If
        End Function

        Public Function insert(ByVal newNode As iterator) As iterator
            If Not newNode Is Nothing Then
                Return insert(+newNode)
            Else
                Return [end]()
            End If
        End Function

        Private Function insert(ByVal newNode As node) As iterator
            If Not newNode Is Nothing Then
                Dim work As node = root
                Dim prev As node = Nothing

                Dim cmp As Int32
                While Not work Is Nothing
                    prev = work
                    cmp = compare(work, newNode)
                    If cmp < 0 Then
                        work = work.rchild
                    ElseIf cmp > 0 Then
                        work = work.lchild
                    Else
                        work.data = +newNode
                        Exit While
                    End If
                End While

                If work Is Nothing Then
                    'assume all newnode is generated by other insert functions,
                    'so do not need to create a new instance here.
                    work = newNode
                    debugassert(work.father() Is Nothing _
                                AndAlso work.lchild() Is Nothing _
                                AndAlso work.rchild() Is Nothing _
                                , "newnode is not a new instance, but with father or lchild or rchild.")
                    If prev Is Nothing Then
                        root = work
                    Else
                        debugassert(cmp <> 0, "should not have cmp = 0 when no node found.")
                        If cmp < 0 Then
                            prev.appendright(work)
                        Else
                            prev.appendleft(work)
                        End If
                    End If
                    nodeCount += 1
                End If

                Return New iterator(work)
            Else
                Return [end]()
            End If
        End Function

        Shared Sub New()
            _end = New iterator(convertor.cast(Of node)(Nothing))
        End Sub

        Public Sub New()
            clear()
        End Sub

        Private Shared Sub copyTreeByNode(ByRef dest As node, ByVal source As node)
            If Not source Is Nothing Then
                dest = New node(+source)
                If Not source.lchild Is Nothing Then
                    Dim subtree As node = Nothing
                    copyTreeByNode(subtree, source.lchild)
                    dest.appendleft(subtree)
                Else
                    dest.appendleft(Nothing)
                End If
                If Not source.rchild Is Nothing Then
                    Dim subtree As node = Nothing
                    copyTreeByNode(subtree, source.rchild)
                    dest.appendright(subtree)
                Else
                    dest.appendright(Nothing)
                End If
            End If
        End Sub

        Private Shared Sub copyTree(ByRef dest As xtree(Of keyType), ByVal source As xtree(Of keyType))
            If Not dest Is Nothing AndAlso Not source.root Is Nothing Then
                copyTreeByNode(dest.root, source.root)
                dest.nodeCount = source.nodeCount
            End If
        End Sub

        Public Overridable Function clone() As Object Implements System.ICloneable.Clone
            Dim rtn As xtree(Of keyType) = Nothing
            rtn = alloc(Me)
            copyTree(rtn, Me)

            Return rtn
        End Function

        Public Delegate Sub traversalAction(ByVal it As iterator)

        Public Enum traversalMethod
            root
            left
            right
        End Enum

        Private Shared Sub dfTraversalImpl(ByVal node As node, ByVal action As traversalAction _
                                         , ByVal method As traversalMethod _
                                         , Optional ByVal startnodeAction As traversalAction = Nothing _
                                         , Optional ByVal finishnodeAction As traversalAction = Nothing)
            debugassert(Not action Is Nothing, "action is nothing.")
            If Not node Is Nothing Then
                Dim it As iterator = Nothing
                it = New iterator(node)
                If Not startnodeAction Is Nothing Then
                    startnodeAction.Invoke(it)
                End If
                Select Case method
                    Case xtree(Of keyType).traversalMethod.root
                        action.Invoke(it)
                        dfTraversalImpl(node.lchild, action, method, startnodeAction, finishnodeAction)
                        dfTraversalImpl(node.rchild, action, method, startnodeAction, finishnodeAction)
                    Case xtree(Of keyType).traversalMethod.left
                        dfTraversalImpl(node.lchild, action, method, startnodeAction, finishnodeAction)
                        action.Invoke(it)
                        dfTraversalImpl(node.rchild, action, method, startnodeAction, finishnodeAction)
                    Case xtree(Of keyType).traversalMethod.right
                        dfTraversalImpl(node.lchild, action, method, startnodeAction, finishnodeAction)
                        dfTraversalImpl(node.rchild, action, method, startnodeAction, finishnodeAction)
                        action.Invoke(it)
                    Case Else
                        debugassert(False, "should cover all possible select.")
                End Select
                If Not finishnodeAction Is Nothing Then
                    finishnodeAction.Invoke(it)
                End If
            End If
        End Sub

        Public Sub dfTraversal(ByVal action As traversalAction, ByVal method As traversalMethod _
                               , Optional ByVal startnodeAction As traversalAction = Nothing _
                               , Optional ByVal finishnodeAction As traversalAction = Nothing)
            dfTraversalImpl(root, action, method, startnodeAction, finishnodeAction)
        End Sub

        Public Sub bfTraversal(ByVal action As traversalAction)
            Dim queue As queue(Of iterator) = Nothing
            queue = New queue(Of iterator)()
            queue.push(New iterator(root))
            While Not queue.empty()
                Dim n As iterator = Nothing
                n = queue.front()
                queue.pop()
                If Not (+n) Is Nothing Then
                    queue.push(New iterator((+convertor.cast(Of pointer(Of node))(n)).lchild))
                    queue.push(New iterator((+convertor.cast(Of pointer(Of node))(n)).rchild))
                    action.Invoke(n)
                End If
            End While
        End Sub

        Private str As String = Nothing

        Private Sub ToStringStart(ByVal it As iterator)
            str += "{"
        End Sub

        Private Sub ToStringEnd(ByVal it As iterator)
            str += "}"
        End Sub

        Private Sub ToStringImpl(ByVal it As iterator)
            str += Convert.ToString(it)
        End Sub

        Public Overrides Function ToString() As String
            str = Nothing
            dfTraversal(AddressOf ToStringImpl, xtree(Of keyType).traversalMethod.root _
                        , AddressOf ToStringStart, AddressOf ToStringEnd)
            Return str
        End Function
    End Class

End Namespace
